package myself.a008CodingTest;

/**
 * @author 叶之越
 * Description 快慢指针问题
 * Date 2021/1/25
 * Time 13:45
 * Mail 739153436@qq.com
 */
public class SpeedPointer {

    public static void main(String[] args) {

    }

    // 输入链表头节点，奇数长度返回中点，偶数长度返回上中点
    // ![](http://img.yhzcmxq.cn/picgo/20210125145006.png)
    public static Node midOrUpMidNode(Node head) {
        if (head == null) {
            return null;
        }
        Node pre = new Node(-1);
        pre.next = head;
        Node next = new Node(-1);
        next.next = head;

        while (next != null) {
            if (next.next != null) {
                pre = pre.next;
            }
            if (next.next == null || next.next.next == null) {
                break;
            }
            next = next.next.next;
        }
        return pre;
    }

    // 输入链表头节点，奇数长度返回中点，偶数长度返回下中点
    // ![](http://img.yhzcmxq.cn/picgo/20210125145943.png)
    public static Node midOrDownMidNode(Node head) {
        if (head == null) {
            return null;
        }
        Node pre = new Node(-1);
        pre.next = head;
        Node next = new Node(-1);
        next.next = head;
        int count = 0;

        while (next != null) {
            if (next.next != null) {
                count++;
                pre = pre.next;
            }
            if (next.next == null || next.next.next == null) {
                break;
            }
            count++;
            next = next.next.next;
        }
        return count % 2 == 0 ? pre.next : pre;
    }

    // 输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
    // ![](http://img.yhzcmxq.cn/picgo/20210125152026.png)
    public static Node midOrUpMidPreNode(Node head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        Node pre = new Node(-1);
        pre.next = head;
        Node next = new Node(-1);
        next.next = head;
        Node mid = pre;

        while (next != null) {
            if (next.next != null) {
                mid = pre;
                pre = pre.next;
            }
            if (next.next == null || next.next.next == null) {
                break;
            }
            next = next.next.next;
        }
        return mid;
    }

    // 输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个
    // ![](http://img.yhzcmxq.cn/picgo/20210125152756.png)
    public static Node midOrDownMidPreNode(Node head) {
        if (head == null || head.next == null) {
            return null;
        }
        if (head.next.next == null) {
            return head;
        }
        Node pre = new Node(-1);
        pre.next = head;
        Node next = new Node(-1);
        next.next = head;
        Node mid = null;
        int count = 0;

        while (next != null) {
            if (next.next != null) {
                count++;
                mid = pre;
                pre = pre.next;
            }
            if (next.next == null || next.next.next == null) {
                break;
            }
            count++;
            next = next.next.next;
        }
        return count % 2 == 0 ? pre : mid;
    }

    public static class Node {
        public int value;
        public Node next;

        public Node(int v) {
            value = v;
        }
    }
}
